1.63

题目

a. Let $A$ be an infinite regular language. Prove that $A$ can be split into two infinite disjoint regular subsets.

b. Let $B$ and $D$ be two languages. Write $B⋐D$ if $B\subseteq D$ and $D$ contains infinitely many strings that are not in $B$. Show that if $B$ and $D$ are two regular languages where $B⋐D$, then we can find a regular language $C$ where $B⋐C⋐D$.

思路

解答